package edu.xidian.sei.mlcs

import scala.collection.mutable.ListBuffer
import java.util.concurrent.RecursiveTask
import scala.collection.mutable.Buffer
import scala.collection.mutable.HashMap
import scala.collection.mutable.HashSet
import scala.collection.mutable.ArrayBuffer
import java.util.concurrent.ForkJoinPool

import java.util.concurrent.ForkJoinTask
import java.util.ArrayList
import edu.xidian.sei.mlcs.util.Stopwatch
import scala.collection.mutable.Queue
import com.carrotsearch.sizeof.RamUsageEstimator

class Graph(val mlcs: MLCS) {
  val location2Nodes = new HashMap[Location, InNode]
  private val keyLocs = new HashSet[Location]() // 关键点
  private var matchedCount: BigDecimal = 0
  // private var maxLevel = -1
  val start: InNode = newNode(mlcs.start)
  val end: InNode = newNode(mlcs.end)

  def newNode(to: Location): InNode = {
    val node = new InNode(to)
    location2Nodes.put(to, node)
    node
  }
  def get(loc: Location): Option[InNode] = location2Nodes.get(loc)

  def size: Int = location2Nodes.size

  def addEdge(start: Location, to: Location): Boolean = {
    val n = location2Nodes.get(to)
    if (n.isEmpty) {
      val node = newNode(to)
      node.inc
      true
    } else {
      val node = n.get
      node.inc
      false
    }
  }

  //  def addLocation(loc: Location): InNode = {
  //    val n = location2Nodes.get(loc)
  //    if (n.isEmpty) {
  //      val node = newNode(loc)
  //      node.indegree = 0.toShort
  //    }
  //    node
  //  }

  def exists(loc: Location): Boolean = location2Nodes.contains(loc)

  def setLevel() {
    var maxLevel = 0

    val pool = if (mlcs.maxThread > 0) new ForkJoinPool(mlcs.maxThread) else new ForkJoinPool()
    val levelQueue = new ListBuffer[Location]()
    levelQueue += mlcs.start
    val parallelism = pool.getParallelism();
    while (!levelQueue.isEmpty) {
      val startTime = System.nanoTime()
      maxLevel += 1
      val countPerSlice = Math.ceil(levelQueue.size * 1.0 / parallelism).toInt
      val locsList = levelQueue.sliding(countPerSlice, countPerSlice)
      val tasks = new ListBuffer[ForkJoinTask[ListBuffer[Location]]]
      locsList.foreach { locs =>
        tasks += pool.submit(new LevelCrawler(this, maxLevel, locs))
      }
      levelQueue.clear
      tasks.foreach(task => levelQueue ++= task.join())
      //println("set level " + maxLevel + " using " + Stopwatch.format(System.nanoTime() - startTime))
    }

    pool.shutdown
  }

  def findKeyLocs() {
    setLevel()
    //    location2Nodes.values.foreach { v =>
    //      println(RamUsageEstimator.sizeOf(v))
    //    }
    keyLocs.clear()
    val keyLocation2Nodes = new HashMap[Location, InNode]()
    val queue = new Queue[Location]

    var tlevel = 0
    // 从虚拟终点到该节点的可选路径数，初始终点为1
    val routeCounts = new HashMap[Location, BigDecimal]()
    routeCounts.put(end.loc, BigDecimal(1))
    var queueEnd = mlcs.end
    queue.enqueue(mlcs.end)
    val maxLevel = (end.level - 1).toShort
    while (!queue.isEmpty) {
      val loc = queue.dequeue();
      val node = get(loc).get;
      node.predecessors.foreach { ploc =>
        val p = get(ploc).get
        if (p.level + tlevel == maxLevel) {
          if (keyLocs.contains(ploc)) {
            routeCounts.put(ploc, (routeCounts(ploc) + routeCounts(loc)))

          } else {
            keyLocs.add(ploc)
            keyLocation2Nodes.put(ploc, p)
            routeCounts.put(ploc, routeCounts(loc))
            queue.enqueue(ploc)
          }
        }
      }
      if (loc == queueEnd) {
        if (!queue.isEmpty) queueEnd = queue.last
        tlevel += 1
      }
    }
    keyLocs.remove(start.loc)
    keyLocs.remove(end.loc)
    keyLocation2Nodes.put(start.loc, start)
    keyLocation2Nodes.put(end.loc, end)
    matchedCount = routeCounts(start.loc)
  }

  def collectPath(n: InNode, suffix: Buffer[Location], result: Buffer[Buffer[Location]]) {
    val maxLevel = n.level - 1
    val predecessors = Buffer[InNode]()
    n.predecessors.foreach { loc =>
      val p = get(loc).get
      if (null != p && p.level == maxLevel) predecessors += p
    }
    predecessors.foreach { e =>
      val newPaths = Buffer[Location]()
      newPaths += e.loc
      newPaths ++= suffix
      if (!e.predecessors.isEmpty) {
        if (e.predecessors.contains(start.loc)) {
          result += newPaths
        } else {
          collectPath(e, newPaths, result)
        }
      }
    }
  }

  def findKeyPaths: Buffer[Buffer[Location]] = {
    val results = Buffer[Buffer[Location]]()
    collectPath(end, Buffer[Location](), results)
    results
  }

  /**
   * 打印路径结果
   */
  def printPathResult {
    findKeyPaths.foreach { path =>
      path.foreach { l => print(mlcs.charAt(l)) }
      println
    }
  }

  /**
   * 统计结果
   */
  def stat: Result = {
    findKeyLocs()
    return new Result(matchedCount, end.level - 1)
  }

}

class LevelCrawler(graph: Graph, level: Int, locations: ListBuffer[Location]) extends RecursiveTask[ListBuffer[Location]] {
  def compute(): ListBuffer[Location] = {
    val nexts = new ListBuffer[Location] //下次拓扑排序的点的层和点集
    locations.foreach { loc => //当前点的loc
      val fromNode = graph.get(loc).get
      val successors = graph.mlcs.nextLocations(loc)
      if (successors.isEmpty) { //后继为空 -> 加入到终点的前驱
        graph.end.addEndPredecessor(fromNode.loc, level)
      } else {
        for (to <- successors) {
          val tempNode = graph.get(to).get
          if (tempNode.addPredecessor(fromNode.loc, level)) {
            nexts += to
          }

        }
      }
    }
    nexts //返回一个层和改层点的映射
  }
}